package java学习.代码随想录.动态规划;
//import com.alibaba.fastjson.JSON;
//import com.alibaba.fastjson.JSONArray;
//import com.alibaba.fastjson.JSONObject;

import com.alibaba.fastjson.JSONObject;
import org.json.JSONArray;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/17 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 一和零 {
    /**
     * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
     *
     * 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
     * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
     *
     * 示例 1：
     * 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3 输出：4
     *
     * 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
     * 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
     * 示例 2： 输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
     */


    /**
     * dp[i][m][n] 不超过m 0 , n 1的最大 字符串数 、
     *
     * dp[i][m][n] = max(dp,dp[i-1][m- 0的数量 ][ n- 1的数量 ])
     */

    public static int findMaxForm(String[] strs, int m, int n) {

        int dp[][] = new int[m+1][n+1];
        for (int i = 0; i < strs.length; i++) {
            int one = 0;
            int zero = 0;
            for (int j = 0; j < strs[i].length(); j++) {
                if (strs[i].charAt(j)=='0') zero++;
                if (strs[i].charAt(j)=='1') one++;

            }

        System.out.println("零："+ zero+"  "+ "一:"+one);

            for (int j = m; j >= zero; j--) {
                for (int k = n; k >=one; k--) {
//                    dp[j][k] 第i个字符串的 容量为 m个1，n个0 的最大子集个数。
                    dp[j][k] = Math.max(dp[j][k],dp[j-zero][k-one] +1); //最大长度
                }
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println(" ");
        }
        return dp[m][n];
    }


    public   static  int findMaxForm1(String[] strs, int m, int n) {
        //dp[i][j]表示i个0和j个1时的最大子集
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            System.out.println("零："+ zeroNum+"  "+ "一:"+oneNum);

            //倒序遍历
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public   static  int findMaxForm2(String[] strs, int m, int n) {
        int[][] array = get01Array(strs);
        int s = strs.length;
        int [] [] [] dp = new int[s+1][m+1][n+1];
//        初始化

//        for (int j = 0; j <=m; j++) {
//            int zero = array[0][0];  // 第0个字符串 0的个数
//            int one = array[0][1];   // 第0个字符串 1的个数
//            for (int k = 0; k <=n; k++) {
//                if (j>=zero && k>=one){
//                    dp[0][j][k] = 1;
//                }
//
//            }
//        }

        for (int i = 1; i <=s; i++) {
            int zero = array[i-1][0];  // 第i个字符串 0的个数 (从0开始)
            int one = array[i-1][1];   // 第i个字符串 1的个数 (从0开始)
            for (int j = 0; j <=m; j++) { // 背包容量

                for (int k = 0; k <= n; k++) {
                    if (j>=zero && k >= one){
                        dp[i][j][k] =Math.max(dp[i-1][j][k],dp[i-1][j-zero][k-one]+1); // 加元素
                    }else {
                        dp[i][j][k] =dp[i-1][j][k]; // 不加元素，就是之前的值
                    }
                }
            }

        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                for (int k = 0; k < dp[0][0].length; k++) {
                    System.out.print(dp[i][j][k]+" ");
                }
                System.out.println(" ");
            }
            System.out.println(" ");

        }
        return dp[s][m][n];
    }
    public static int findMaxForm3(String[] strs, int m, int n) {
        int len = strs.length;
        // 预处理每一个字符包含 0 和 1 的数量
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    zero++;
                } else {
                    one++;
                }
            }
            cnt[i] = new int[]{zero, one};
        }

        // 处理只考虑第一件物品的情况
        int[][][] f = new int[len][m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[0][i][j] = (i >= cnt[0][0] && j >= cnt[0][1]) ? 1 : 0;
            }
        }

        // 处理考虑其余物品的情况
        for (int k = 1; k < len; k++) {
            int zero = cnt[k][0], one = cnt[k][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    // 不选择第 k 件物品
                    int a = f[k-1][i][j];
                    // 选择第 k 件物品（前提是有足够的 m 和 n 额度可使用）
                    int b = (i >= zero && j >= one) ? f[k-1][i-zero][j-one] + 1 : 0;
                    f[k][i][j] = Math.max(a, b);
                }
            }
        }
        for (int i = 0; i < f.length; i++) {
            for (int j = 0; j < f[0].length; j++) {
                for (int k = 0; k < f[0][0].length; k++) {
                    System.out.print(f[i][j][k]+" ");
                }
                System.out.println(" ");
            }
            System.out.println(" ");

        }
        return f[len-1][m][n];
    }

    public static void main(String[] args) {
        String[] str = {"10","0001","111001","1","0"};
//        System.out.println(findMaxForm(str, 5, 3));
//        System.out.println(findMaxForm1(str, 5, 3));
       String[] str1 =  {"10","0","1"};
        System.out.println(findMaxForm1(str1, 1, 1));

        System.out.println(findMaxForm2(str1, 1, 1));
        System.out.println("---");
        System.out.println(findMaxForm3(str1, 1, 1));

//        int[][] array = get01Array(str);
//        for (int i = 0; i < array.length; i++) {
//            for (int j = 0; j < array[0].length; j++) {
//                System.out.print(array[i][j]+" ");
//            }
//            System.out.println(" ");
//        }
    }
    public static int[][] get01Array(String[] strs) {
        int [][] ans = new int[strs.length][ ];
        for (int i = 0; i < strs.length; i++) {
            int one = 0;
            int zero = 0;
            for (int j = 0; j < strs[i].length(); j++) {
                if (strs[i].charAt(j)=='0') zero++;
                if (strs[i].charAt(j)=='1') one++;
                ans[i] = new int[]{ zero,one }; // 记录每个字符串的01个数
            }
        }
        return ans;
    }


}
